import java.util.LinkedList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
  }
public class LeetCode {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null){
            return root;
        }
        if(p==root||q==root){
            return root;
        }
        //P、Q都不为root且不为空
        TreeNode Left=lowestCommonAncestor(root.left,p,q);
        TreeNode Right =lowestCommonAncestor(root.right,p,q);
        if(Left!=null&&Right!=null){
            return root;
        }
        //Left与Rihet在一边
        if (Left!=null){
            return Left;
        }else {
            return Right;
        }
    }
//根据前序中序返回根
    public  int pre;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root=BuildTree(preorder,inorder,0,inorder.length-1);
        return root;
    }
    public TreeNode BuildTree(int[] preorder, int[] inorder,int inbegin,int inend){
        if(inbegin>inend){
            return null;
        }
        TreeNode root=new TreeNode(preorder[pre]);
        int find=Find(inorder,inbegin,inend,preorder[pre]);
        if(find==-1){
            return null;
        }
        pre++;
        root.left=BuildTree(preorder,inorder,inbegin,find-1);
        root.right=BuildTree(preorder,inorder,find+1,inend);
    return root;
    }
    public int Find( int[] inorder,int inbegin,int inend,int node){
        for (int i=inbegin;i<=inend;i++){
            if (inorder[i]==node){
                return i;
            }
        }
        return -1;
    }
    //根据中序后序返回根
    int post=0;
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        TreeNode root=BuildTree(inorder,postorder,0,inorder.length-1);
        return root;
    }
    public TreeNode BuildTree2(int[] inorder, int[] postorder,int inbegin,int inend){
        post=postorder.length-1;
        if(inbegin>inend){
            return null;
        }
        TreeNode root=new TreeNode(postorder[post]);
        int find=Find(inorder,inbegin,inend,postorder[post]);
        if(find==-1){
            return null;
        }
        post--;
        root.left=BuildTree(inorder,postorder,inbegin,find-1);
        root.right=BuildTree(inorder,postorder,find+1,inend);
        return root;
    }



}

